package com.maltys.monotonic.stack;

import java.util.Stack;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/trapping-rain-water/">接雨水</a>
 */
public class TrappingRainWater {
    public static void main(String[] args) {
        TrappingRainWater rainWater = new TrappingRainWater();
        int trap = rainWater.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
        System.out.println(trap);
    }

    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 当前凹槽
                Integer idx = stack.pop();
                if (!stack.isEmpty()) {
                    // 凹槽的左边界 和 右边界的最小值 - 凹槽的高度 代表横向的高度
                    int high = Math.min(height[stack.peek()], height[i]) - height[idx];
                    // 凹槽的宽度
                    int width = i - stack.peek() - 1;
                    result += high * width;
                }
            }
            stack.push(i);
        }
        return result;
    }
}
